\documentclass[a4paper,12pt]{article}
\renewcommand{\baselinestretch}{1.0}
\usepackage[utf8]{inputenc}
\usepackage[brazil]{babel}
\usepackage{verbatim}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{epsfig}
\usepackage{subfigure}
% \usepackage[pdftex]{graphicx}
%%%%%%%%%%%%%%%%%%%%%%%%

% 
\usepackage{listings}

\lstset{
stringstyle=\ttfamily,
language=C,
frame=single,
showstringspaces=false,
breaklines=true,
basicstyle=\footnotesize,
firstnumber=1,
numbers=left,
stepnumber=1,
numberstyle=\tiny,
xrightmargin=-20pt,
xleftmargin=-10pt
}


\begin{document}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%		CAPA
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{titlepage}
\begin{center}
      {\large Universidade Federal de Minas Gerais \\
           Belo Horizonte, 1\textordmasculine \hspace{0.02cm} semestre de 2011 \\}
\vspace{5cm}
{\Huge \sc Trabalho Prático 2\\}
\vspace{0,5cm}
{\Huge \textbf{ Processamento de Consultas }\\}
\vspace{1,2cm}
{\large Recuperação de Informação - Máquinas de Busca na Web \\}
\vspace{6cm} 
{\tt \large Lucas Cunha de Oliveira Miranda \\}
\begin{small}\textit{lucmir@dcc.ufmg.br} \end{small}
\end{center}
\end{titlepage}

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%		SUMÁRIO
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\tableofcontents

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%		INTRODUÇÃO
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{center}
 {\LARGE Trabalho Prático 2\\}
 {\Large \it Processamento de Consultas\\}
\end{center}
\vspace{1cm}

\section{Introdução}
O grande volume de dados disponíveis no formato digital gerou, recentemente, um cenário paradoxal, em
que, o excesso de informações prejudica o acesso a conteúdos relevantes. 
Neste contexto, uma área da computação que vem despertando muito interesse é a Recuperação de Informação. 
RI é uma ciência que lida com o armazenamento de documentos e a recuperação automática de informações associadas a eles.
O problema de extrair informações relevantes de uma coleção de documentos não é trivial.
Além das dificuldades técnicas da área, existem as complicações relacionadas com o problema de semântica.
Por exemplo, para obter documentos de seu interesse, um usuário deve traduzir uma necessidade de informação em uma consulta.\\

\noindent Uma forma simples de obter um conjunto de respostas para uma consulta de usuário é determinar quais documentos em uma coleção
 contêm palavras-chaves passadas pelo usuário que resumem sua necessidade.
A maioria dos sistemas para recuperação de informação em arquivos constituídos de texto empregam a técnica de construção de um índice que 
suportam consultas sobre ocorrências de palavras-chaves \cite{witten1999managing}. O trabalho prático 1 consistiu na implementação de um 
sistema para geração e utilização de um índice. Este foi construído no formato de um 
``arquivo invertido'', uma estrutura constituída de uma lista ordenada de palavras-chaves, onde cada palavra-chave tem
uma lista de apontadores para os documentos que contêm aquela palavra-chave.\\ 
% O emprego de arquivos invertidos já provou ser até várias ordens de magnitude mais eficiente que algoritmos simples de pesquisa.

\noindent O emprego de arquivos invertidos permite a busca eficiente por todos os documentos de um domínio 
que possuem as palavras-chaves assinaladas pelo usuário. Entretanto, essa informação não é suficiente.
É necessário ordenar os documentos por relevância ou similaridade em relação à consulta realizada.
O trabalho prático 2 consiste na implementação de um processador de consultas que, 
utilizando o sistema de construção e pesquisa em arquivos invertidos do TP1, seja capaz de realizar ordenação de documentos.

\subsection{Proposta}
O Trabalho Prático 2 propõe a implementação de um sistema capaz de processar consultas
sobre um grande número de documentos e retornar um subconjunto deste domínio ordenado por potencial de relevância ({\it ranking}). 
Para determinar a similaridade entre uma consulta e os documentos da coleção, devem ser implementados o modelo de espaço vetorial e o modelo BM25.
A qualidade dos {\it rankings} gerados deve ser avaliada por meio de curvas de precisão versus revocação para um conjunto de 
consultas e documentos relevantes disponibilizados para o trabalho prático. 

\section{Solução}

O trabalho prático 2 constitui uma solução para o problema de extrair um {\it ranking} 
de documentos ordenados por potencial de relevância a partir de consultas fornecidas pelo usuário.
O desenvolvimento do TP 2 envolveu uma fase de estudo e projeto da solução, seguido de um 
processo de avaliação dos recursos necessários e da estruturação do sistema, antes das 
etapas de implementação e avaliação experimental.\\

\noindent O programa implementado no trabalho prático 1 foi aproveitado para a geração do arquivo invertido, 
necessário para a execução eficiente de consultas por termos na coleção de documentos. 
Foram necessárias apenas algumas modificações neste código para permitir o pré-processamento de informações
relevantes para o cálculo do {\it ranking}. 
Além disso, o desenvolvimento do trabalho prático 2 envolveu a implementação de um programa para 
processamento de consultas, que utiliza como entrada o índice gerado pelo sistema modificado do trabalho anterior, e 
a disponibilização de uma interface web para realização de consultas. 
Após a implementação do trabalho, realizou-se um procedimento final de testes e avaliação experimental.
A qualidade dos modelos implementados foi verificada considerando as métricas tradicionais de precisão e revocação.

\subsection{Ambiente e Recursos}

O trabalho foi implementado na linguagem de programação C++. 
Todo o desenvolvimento foi realizado em plataforma Linux (Ubuntu 11.04).
Foram empregados, no programa de geração de índice, implementado no Trabalho Prático 1 e necessário para o TP2, 
além das bibliotecas padrões, o parser público {\it htmlcxx} \cite{htmlcxx} e
um conjunto de classes para a leitura dos documentos compactados \cite{ricode}.
O sistema de processamento de consultas utiliza apenas as bibliotecas padrões disponíveis na linguagem.
% A interface web para realização de consultas foi implementada utilizando html e javascript (com jquery) e 
% foi instalada em um servidor Apache.  A comunicação entre a interface e o programa em C++ foi feita 
% através da biblioteca wt () [referência].

\subsection{Implementação}
A modelagem em RI é um processo que objetiva a produção de uma função de ordenação ({\it ranking function})
que seja capaz de associar um grau de relevância ({\it scores}) para documentos, dada uma consulta de um usuário.
Este processo consiste, essencialmente, de duas tarefas: a representação dos documentos e da consulta e a
elaboração de uma função ({\it ranking function}) que permite quantificar a similaridade entre documento e consulta.\\

\noindent O processo de recuperar um {\it ranking} envolve, em geral, os seguintes passos:
\begin{itemize}
 \item interpretação da consulta do usuário como um conjunto de termos representativos ou palavras-chave;
 \item busca por documentos relacionados com cada termo na coleção (pesquisa no índice);
 \item cálculo de similaridade entre os documentos recuperados e os termos da consulta;
 \item ordenação dos documentos pela similaridade no formato de um {\it ranking}.
\end{itemize}

% talvez colocar figura
\noindent O Trabalho Prático 2 foi implementado como um programa em C++ capaz
de realizar ordenação ({\it ranking}) utilizando o modelo de espaço vetorial
e o modelo BM25.

\subsubsection{O modelo vetorial}

O modelo vetorial consiste na representação de documentos e consultas como vetores em um espaço $n-$dimensional,
atribuindo pesos aos seus termos indexados. Os documentos são, então, ordenados em ordem decrescente de 
similaridade calculada sobre seus vetores e o vetor que representa a consulta.\\

\noindent As representações do documento $d_j$ e da consulta $q$ são vetores $t-$dimensionais do tipo:
$$d_j = (w_{1,j},w_{2,j},...,w_{t,j})$$  $$q = (w_{1,q},w_{2,q},...,w_{t,q})$$\\

\noindent A similaridade entre $d_j$ e $q$ é dada pelo cálculo do cosseno de suas representações vetoriais:
$$sim(d_j, q) = cos(\theta) = \frac{\vec{d_j}\cdot\vec{q}}{|\vec{d_j}|\times|\vec{q}|} = 
\frac{\sum _{i=1}^N w_{i,j}  w_{i,q}}{W_d W_q}$$\\  
\noindent onde $W_d = \sqrt{\sum _{i=1}^n w_{i,j}^2} $ e $W_q = \sqrt{\sum _{i=1}^n w_{i,q}^2}$\\ 

\noindent Um método simples e eficiente para definição dos pesos é utilizar o TF x IDF. 
A fórmula para cálculo da similaridade fica, portanto:
$$sim(d_j, q) = \frac{1}{W_d W_q}\sum_{t\in Q\cap D_d}{(1 + log_ef_{d,t}) log_e(1 + \frac{N}{f_t})}$$

\noindent Para implementar o cálculo de similaridade empregando o modelo vetorial, 
a frequência $f_t$ de cada termo (em número de documentos) deve ser obtida diretamente
do vocabulário no momento da consulta. Além disso, é necessário que o número de ocorrências de um termo em cada
documento $f_{d,t}$ esteja presente no arquivo invertido.\\

\noindent O termo $W_q$ da expressão, por ser constante para uma dada consulta, pode ser desprezado sem afetar o {\it ranking}.
Entretanto, o componente $W_d$ deve ser computado e exige que os valores de $f_t$ e $f_{d,t}$ de cada termo presente
no documento sejam conhecidos. Como estes valores só podem ser obtidos após a leitura de toda coleção, 
o custo para o cálculo de $W_d$ para todos os documentos da coleção é quadrático ($O(N^2)$). Ou seja, 
é necessário que todos os documentos sejam lidos e que o cálculo seja efetuado para cada documento após a 
leitura completa da coleção.\\

\noindent Para que a consulta seja eficiente, os pesos devem ser pré-calculados.
O código de geração do índice foi, portanto, modificado para efetuar o cálculo do peso atribuído para cada documento.
Para tanto, a frequência de cada termo passou a ser registrada no momento da leitura da coleção e a ponderação 
por documento passou a ser implementada na etapa de escrita do índice (quando as frequências de cada termo são conhecidas).
Assim, o termo $f_t$ é obtido diretamente do vocabulário e os componentes $f_d,t$ são obtidos por uma consulta direta
ao arquivo invertido e o termo $W_d$ é recuperado diretamente de uma tabela {\it hash} pré-calculada e indexada pelo identificador do documento.\\

\noindent O pseudocódigo \ref{algvm} resume a implementação do cálculo da similaridade pelo modelo vetorial.\\

 \begin{small}
 \begin{algorithm}
 \caption{Algoritmo de cálculo da similaridade pelo modelo vetorial}
 	\begin{algorithmic}
		\STATE {Inicializa acumuladores $A$}
 		\FORALL {termo $t \in Q$}
			\STATE {Obtém $f_{t}$ do vocabulário}
			\STATE {Calcula $w_t = 1 + log_e(N/f_t)$}
 			\FORALL {$(d,f_{d,t})$ do arquivo invertido indexado para $t$}
 				\STATE {Calcula $a = log_e(1 + f_{d,t})w_t$ }
 				\STATE {Faz $A_d = A_d + a$ se $A_d \in $ ou $A_d = a$ caso contrário}
 			\ENDFOR
 		\ENDFOR
		\FORALL {termo $A_d \in A$}
		    \STATE {$A_d = A_d/W_d$}
		\ENDFOR
 		\STATE {Ordenar documentos por $A_d$ ou extrair documentos com maior $A_d$}
 	\end{algorithmic}
 \label{algvm}
 \end{algorithm}
\end{small}

\noindent A implementação do calculo da similaridade entre documento e consulta exige uma estrutura
indexada pelo identificador do documento para acumular os valores que formam o {\it score} de cada documento.
Para cada termo da consulta, calcula-se o seu peso $w_t$ e, para cada documento contendo o termo, agrega-se
o valor de $log_e(1 + f_{d,t})w_t$ na pontuação do documento. Por último, a pontuação de cada documento é 
obtida pela divisão do valor acumulado correspondente pelo peso pré-calculado $W_d$. O {\it ranking} 
é obtido pela ordenação do conjunto $A$ ou pela obtenção dos documentos com maiores valores para $A_d$.\\

\noindent O algoritmo exige que, para cada termo, seja realizada uma consulta no vocabulário ($O(1)$), 
uma consulta no índice ($O(1)$) e um cálculo para cada documento em que o termo está presente. Portanto, 
a complexidade do método em função do número de termos distintos é $O(N)$. Mas deve ser observado que
o número médio de documentos por termo é um fator constante que pesa sobre o aumento da quantidade de termos em uma consulta.
Sendo $\bar{f_t}$ a frequência média de cada termo, $N$ o número de termos distintos e $|D|$ o número de documentos na coleção, a função de complexidade 
para o algoritmo em questão é do tipo $\bar{f_t}\times N + |D|$ para cada consulta. 
Além do custo do cálculo da similaridade entre documentos, existe o custo da ordenação para geração do {\it ranking}, que
é de complexidade $O(NlogN)$ \cite{cormen2001introduction} quando todo conjunto $A$ é ordenado (sendo $N$, neste caso, o número de documentos retornados).

\subsubsection{O modelo BM25}

\noindent O modelo BM25 ({\it Best Match 25}) foi derivado de uma série de experimentos em variações do modelo 
probabilístico. O modelo é baseado nas métricas de IDF {\it inverse document frequency}, TF ({\it term frequency}) e 
normalização pelo tamanho do documento.\\

\noindent A função de {\it ranking} para o modelo BM25 que provê a similaridade entre um documento e uma consulta é descrita 
pela seguinte expressão:
$$sim_{BM25}(d_j,q) ~ \sum_{k_i[q,d_j]}{B_{i,j} \times log(\frac{N-n_i+0.5}{n_i + 0.5})}$$
em que $B_{i,j}$ é um fator da frequência de um termo e pode ser definido como: 
$$B_{i,j} = \frac{(K + 1)f_{i,j}}{K[(1-b) + b\frac{len(d_j)}{avgDocLen}]+f{i_j}}$$
Os termos $K$ e $b$ são constantes e o termo $\frac{len(d_j)}{avgDocLen}$ é calculado dividindo-se o tamanho do documento
pelo tamanho médio dos documentos.\\

\noindent Para implementar o cálculo da similaridade segundo o modelo BM25 de maneira eficiente, foi necessário
pré-calcular, no momento da geração do índice, o termo que quantifica o tamanho de cada documento.
Os demais parâmetros necessários foram obtidos, no momento da consulta, por meio de consultas ao 
vocabulário ou ao índice.\\

\noindent O pseudocódigo \ref{algbm25} resume a implementação do cálculo da similaridade pelo modelo BM25.\\

 \begin{small}
 \begin{algorithm}
 \caption{Algoritmo de cálculo da similaridade pelo modelo BM25}
 	\begin{algorithmic}
		\STATE {Inicializa acumuladores $A$}
		\STATE {Define $K$ e $b$}
 		\FORALL {termo $t \in Q$}
			\STATE {Obtém $f_{t}$ do vocabulário}
 			\FORALL {$(d,f_{d,t})$ do arquivo invertido indexado para $t$}
				\STATE {Obtém $\frac{len(d)}{avgDocLen}$ pré-calculado}
				\STATE {Calcula $B_{i,j}$ }
				\STATE {Calcula $a = B_{i,j} \times log(\frac{N-f_{t}+0.5}{f_t+0.5})$}
 				\STATE {Faz $A_d = A_d + a$ se $A_d \in $ ou $A_d = a$ caso contrário}
 			\ENDFOR
 		\ENDFOR
 		\STATE {Ordenar documentos por $A_d$ ou extrair documentos com maior $A_d$}
 	\end{algorithmic}
 \label{algbm25}
 \end{algorithm}
\end{small}

\noindent O algoritmo para cálculo da similaridade entre documento e consulta pelo modelo BM25 utiliza uma
estrutura de acumuladores igual à empregada no modelo vetorial.
Para cada termo da consulta, a frequência $f_t$ e a entrada para o índice são obtidos diretamente do vocabulário (a custo $O(1)$).
Para cada documento em que o termo ocorre, calcula-se $B_{i,j}$ utilizando a ponderação por tamanho do documento, 
já pré-calculada e obtida de uma tabela {\it hash} (indexada pelo identificador do documento), a constante $K$ e o valor de $f_{i,d}$.
O fator a ser acumulado para formação da similaridade é calculado considerando $B_{i,j}$, $b$ e $f_t$.
Por fim, os documentos são ordenados pelos acumuladores.\\

\noindent De forma similar ao algoritmo do modelo vetorial, o método segundo o BM25 exige que, para cada termo, 
sejam realizadas operações de consulta sobre vocabulário e índice (ambas $O(1)$) e um cálculo para cada documento 
em que o termo está presente. Portanto, a complexidade do método em função do número de termos distintos 
também é $O(N)$. Neste caso, sendo $\bar{f_t}$ número médio de documentos por termo
e $N$ o número de termos distintos, a função de complexidade para o algoritmo em questão é do tipo $\bar{f_t}\times N$. 
Além do custo do cálculo da similaridade entre documentos, também existe o custo da ordenação para geração do {\it ranking}, que
é de complexidade $O(NlogN)$ quando todo conjunto $A$ é ordenado (sendo $N$, neste caso, o número de documentos que 
contêm pelo menos um termo da consulta).

\subsubsection{Decisões de implementação}
As especificações de requisitos não preveem muitas das decisões que devem ser tomadas durante a fase de implementação do sistema.
Durante o desenvolvimento do trabalho surgiram muitas questões que exigiram que fossem feitas certas escolhas.
As decisões de implementação mais relevantes para este TP 2 foram:
\begin{itemize}
  \item O {\it ranking} é obtido por um processo de extração dos $r$ documentos com maior pontuação. 
Este procedimento é de complexidade $O(N^2)$ se for necessário retornar o {\it ranking} completo.
Entretanto, esta decisão foi tomada já que o valor de $r$ é parametrizável e, na maioria das vezes, o 
usuário está interessado em um número reduzido de documentos como resposta de uma consulta.
  \item Os valores de pontuação para cada documento no {\it ranking} são calculados mas não são exibidos para o usuário.
A definição da diretiva PRINT\_SCORE no arquivo {\it src/RankBuilder.h} faz com que os {\it scores} também façam parte do resultado
da consulta.
  \item Os parâmetros do modelo BM25 foram definidos como $K=1$ e $b=0.75$. 
Os experimentos descritos na literatura variando estes parâmetros relatam um bom funcionamento do algoritmo para aplicações reais.
Se for necessário modificá-los, basta redefinir os valores das constantes BM25\_K e BM25\_B no arquivo {src/RankBuilder.h}.
  \item O tamanho do documento, necessário para os cálculos do modelo BM25, foi assumido como sendo a soma das ocorrências 
de cada termo no documento. O algoritmo emprega este valor dividido pelo tamanho médio de documento para a coleção.
\end{itemize}


\section{Operação do Programa}

O trabalho prático foi implementado 
como um programa em C++ que permite a execução de consultas para
obtenção de um {\it ranking} de documentos ordenados por similaridade com o que foi consultado.
Para efetuar buscas eficientes sobre coleções grandes de documentos, foi utilizado um 
programa adaptado do trabalho prático 1 para a geração do índice, do vocabulário e
das informações sobre os documentos.

\subsection{Compilação}

A compilação dos programas pode ser executada pelo utilitário \textit{Make} no diretório {\it src}. 
O arquivo \textit{Makefile} contém as definições necessárias para compilar o código.
As bibliotecas que não são padrões (dependências dos programas implementados) foram incluídas no código: 
diretórios \textit{src/index/riCode} e \textit{src/index/htmlcxx-0.84}. O comando:
\begin{footnotesize}
  \begin{verbatim}
       make all
  \end{verbatim}
\end{footnotesize}
\vspace{-0.4cm}
executa a compilação dos dois sistemas, gerando os arquivos executáveis \textit{./src/bin/index}, para o programa construtor de arquivos invertidos,
e \textit{./src/bin/rank} para o processador de consultas:
\begin{footnotesize}
  \begin{verbatim}
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall index/riCode/src/Document.cpp -o bin/Document.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall index/riCode/src/CollectionReader.cpp -o bin/CollectionReader.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall index/Registry.cpp -o bin/Registry.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall index/Run.cpp -o bin/Run.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall index/Lexon.cpp -o bin/Lexon.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall index/Parser.cpp -o bin/Parser.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall index/IndexBuilder.cpp -o bin/IndexBuilder.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall index/Encoder.cpp -o bin/Encoder.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall index/Index.cpp -o bin/Index.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall index/QueryResult.cpp -o bin/QueryResult.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall index/TimeMeasurement.cpp -o bin/TimeMeasurement.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall index/DocumentInfo.cpp -o bin/DocumentInfo.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall index/DocumentIndex.cpp -o bin/DocumentIndex.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall index/IndexMain.cpp -o bin/IndexMain.o
g++ bin/Document.o bin/CollectionReader.o bin/Registry.o bin/Run.o 
    bin/Lexon.o bin/Parser.o bin/IndexBuilder.o bin/Encoder.o
    bin/Index.o bin/QueryResult.o bin/TimeMeasurement.o 
    bin/DocumentInfo.o bin/DocumentIndex.o bin/IndexMain.o 
    `pwd`/index/htmlcxx-0.84/lib/*.o -lz -L `pwd`/index/htmlcxx-0.84/lib
    -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -o bin/index 	

g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall RankBuilder.cpp -o bin/RankBuilder.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2 
    -Wall Rank.cpp -o bin/Rank.o
g++ -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -c -O2
    -Wall RankMain.cpp -o bin/RankMain.o
g++ bin/Registry.o bin/Run.o bin/Lexon.o bin/Parser.o bin/Document.o 
    bin/CollectionReader.o bin/IndexBuilder.o bin/Index.o bin/Encoder.o
    bin/QueryResult.o bin/TimeMeasurement.o bin/DocumentInfo.o
    bin/DocumentIndex.o bin/RankBuilder.o bin/Rank.o bin/RankMain.o 
    `pwd`/index/htmlcxx-0.84/lib/*.o -lz -L `pwd`/index/htmlcxx-0.84/lib
    -I index/riCode/src -I `pwd`/index/htmlcxx-0.84/include -o bin/rank
  \end{verbatim}
\end{footnotesize}
\vspace{-0.4cm}
Os programas também podem ser compilados individualmente pelos seguintes comandos:
\begin{footnotesize}
  \begin{verbatim}
       make index
       make rank
  \end{verbatim}
\end{footnotesize}
\vspace{-0.4cm}
Os objetos resultantes da compilação (e da execução) podem ser removidos pelo uso do comando:
\begin{footnotesize}
  \begin{verbatim}
       make clean
  \end{verbatim}
\end{footnotesize}
\vspace{-0.4cm}
A dependência do diretório \textit{src/index/riCode} é compilada juntamente com os programas. 
Entretanto, o código em \textit{src/index/htmlcxx-0.84} não é compilado pelo comando \textit{make all}, sendo apenas ``\textit{linkado}'' na compilação.
Caso seja necessário, os seguintes comandos, se executados no diretório {\it src/index}, podem ser utilizados para compilar individualmente a biblioteca \textit{htmlcxx}:
\begin{footnotesize}
  \begin{verbatim}
       make htmlcxx_clean
       make htmlcxx
  \end{verbatim}
\end{footnotesize}
\vspace{-0.4cm}
Os arquivos gerados na compilação podem ser executados em um terminal por linha de comando.

\subsection{Execução}

O programa que constrói o índice pode ser rodado pela execução do arquivo \textit{./bin/index}.\\

\noindent A execução exige a passagem dos seguintes parâmetros:
\begin{footnotesize}
\begin{description}
\item [-i] (entrada) nome do arquivo de entrada contendo o índice de documentos.
\item [-f] (entrada) caminho para diretório com documentos.
\item [-t] (saída) caminho para diretório para arquivos temporários.
\item [-a] (saída) caminho para arquivo invertido a ser gerado.
\item [-v] (saída) caminho para arquivo com vocabulário.
\item [-d] (saída) arquivo com relação de documentos e identificadores.
\end{description}
\end{footnotesize}
\vspace{0.4cm}
Segue um exemplo de execução:
\begin{footnotesize}
\begin{verbatim}
    ./bin/index -i indexToCompressedColection.txt -f test/input/toyExample 
            -t test/output/ -a test/output/index -v test/output/vocabulary
            -d test/output/documents
\end{verbatim}
\end{footnotesize}
\vspace{0.2cm}
O programa que processa consultas e gera o {\it ranking} pode ser rodado pela execução do arquivo \textit{./bin/rank}.\\

\noindent A execução exige a passagem dos seguintes parâmetros:
\begin{footnotesize}
\begin{description}
\item [-a] caminho para arquivo invertido gerado.
\item [-v] caminho para arquivo com vocabulário.
\item [-d] arquivo com relação de documentos e identificadores.
\end{description}
\end{footnotesize}

\vspace{0.4cm}
\noindent Parâmetros opcionais:
\begin{footnotesize}
\begin{description}
\item [-m] modelo utilizado: 
  \begin{description}
    \item A/a para executar todos (opção default).
    \item B/b para modelo BM25.
    \item V/v para modelo Vetorial.
    \item C/c para modelo combinado de BM25 e Vetorial.
  \end{description}
\item [-l] tamanho do {\it ranking} em número de documentos (todos os documentos como default).

\end{description}
\end{footnotesize}

\vspace{0.4cm}
\noindent Todos os parâmetros obrigatórios são caminhos para arquivos gerados por uma execução anterior do programa que constrói o índice.
Segue um exemplo de execução:
\begin{footnotesize}
\begin{verbatim}
    ./bin/rank -a test/output/index -v test/output/vocabulary 
             -d test/output/documents -m b -l 3
\end{verbatim}
\end{footnotesize}
A execução do programa também pode ser feita pelo utilitário \textit{Make}. 
Mas, os parâmetros utilizados serão os que foram pré-definidos no arquivo \textit{Makefile}. O comando:
\begin{footnotesize}
\begin{verbatim}
    make run
\end{verbatim}
\end{footnotesize}
compilará, se necessário, e executará os programas sequencialmente com os dados estabelecidos no arquivo \textit{Makefile}.
Foram definidas entradas de tamanho reduzido para a execução desta forma.

\subsection{Entrada}
As entradas para o programa que gera o arquivo invertido envolvem um arquivo com índice de documentos e arquivos de texto compactados.
O formato dos documentos segue a especificação do trabalho.\\

\noindent As entradas para o programa processador de consultas são saídas inalteradas do programa que executa a geração do arquivo invertido.
As consultas são realizadas de forma interativa. Toda requisição é seguida pela resposta e pelo tempo consumido na consulta.

\subsection{Saída}

A execução do programa responsável por construir o arquivo invertido gera, como saída, 3 arquivos.
O índice (arquivo invertido) gerado é um documento escrito no modo binário para facilitar a indexação.
O arquivo contendo o vocabulário possui informações sobre cada termo distinto extraído dos documentos:
valor, identificador, posição no arquivo invertido e frequência ($TF$). 
Além disso, é gerado um arquivo contendo as relações entre os identificadores dos documentos e o 
seu valor (URL do documento) e informações pré-processadas sobre cada documento para agilizar o processo de geração do {\it ranking}.\\

\noindent O programa processador de consultas possui uma interface interativa. 
O usuário pode inserir consultas formatadas como sentenças contendo termos separados por espaço. 
A resposta é exibida na tela e contêm as urls dos documentos ordenados por relevância.
Para encerrar o programa, o usuário deve digitar ``\textit{EXIT/exit}''\\

\noindent Segue um exemplo de execução de uma consulta:\\
\begin{footnotesize}
\begin{verbatim}
./bin/rank -a test/output/index -v test/output/vocabulary 
      -d test/output/documents -m b -l 3

Carregando vocabulário...			[  OK  ]
Carregando informações dos documentos...	[  OK  ]

--------------------------------------------------

Digite sua consulta ("exit/EXIT" para sair): 	

Rank pelo Modelo BM25:
	1) http://www.mrjogos.com.br/games-gratis-online/tiro/the-professinals/
	2) http://www.mrjogos.com.br/games-gratis-online/tiro/tiro-para-o-ouro/
	3) http://tutomania.com.br/file.php?cod=20940

	Tempo consumido: usr:0.000000s / sis:0.000000s / tot:0.000000s

--------------------------------------------------

Digite sua consulta ("exit/EXIT" para sair): exit

--------------------------------------------------
\end{verbatim}
\end{footnotesize}

\subsection{Interface para consultas}
Além do programa para processamento de consultas por meio de linha de comando, também foi implementada uma interface gráfica.
\begin{figure}[!ht]
% \centering
   \includegraphics[scale=0.34]{img/interface.eps}
\caption{Interface para consultas}
\label{interface}
\end{figure}
A figura \ref{interface} mostra o uso da interface para execução de uma consulta.\\

\noindent O programa para geração do {\it ranking} é, essencialmente, o mesmo que permite as execuções via linha de comando.
Entretanto, uma versão deste sistema foi equipada com funções para comunicação via {\it sockets}, permitindo
que o programa fique ``escutando'' em uma porta por requisições e as responda com o resultado do {\it ranking}.
A interface foi construída como uma página formada por um formulário html simples (com apenas o campo da consulta).
A comunicação entre a interface e o programa processador de consultas foi implementada por meio de um {\it script CGI} \cite{cgi}.\\

\noindent A interface para consultas foi implementada e executada localmente. 
Não foi possível disponibilizá-la para consultas externas
por falta de um ambiente que fique disponível para a execução dos programas no servidor e que 
possua espaço suficiente para armazenar o índice da coleção.

\section{Avaliação Experimental}
Foram realizados experimentos para avaliar o comportamento dos modelos implementados para geração de {\it ranking}.
Todos os testes foram executados em um computador {\it Intel Core 2 Duo}, 2.00GHz, 3 Gigabyte de memória RAM 
e plataforma {\it Linux Ubuntu 11.04}. Os testes foram executados sobre uma coleção com 945642 documentos, 
contida em DVD e disponibilizada para os alunos da disciplina.\\

\noindent Para avaliar a efetividade dos {\it rankings} obtidos com o programa implementado, foram geradas as curvas de revocação x precisão
\cite{makhoul99performance} para um conjunto de 30 consultas fornecidas na especificação do trabalho.
 Também foram fornecidos os conjuntos de documentos relevantes para cada consulta.
Foram avaliados os algoritmos utilizando o modelo vetorial, o modelo BM25 e uma combinação destes dois modelos.

\subsection{Combinação dos modelos}
O modelo vetorial e o modelo BM25 foram combinados com o objetivo de aproveitar os aspectos positivos 
de cada abordagem. O modelo BM25 possui o diferencial de considerar o tamanho dos documentos 
em sua fórmula. Como o modelo vetorial não considera este parâmetro, documentos com muitos termos
podem ter uma influência significativa no {\it ranking}. Por outro lado,
o modelo vetorial utiliza, como informação relevante, o peso do documento (módulo do vetor que representa o documento).\\

\noindent Foram realizadas várias tentativas de combinação dos modelos. 
A avaliação dos gráficos de revocação x precisão para as abordagens combinadas foi utilizada como critério de escolha.
Para combinar os modelos, o algoritmo de cálculo acumulado dos {\it scores} foi mantido, mas, 
foi tomada uma média ponderada dos valores calculados pelo modelo BM25 e pelo modelo vetorial. 
A ponderação de cada modelo foi variada e os resultados foram comparados. Os melhores valores obtidos
foram um fator de 1.4 favorecendo a ponderação obtida com o modelo BM25.


\subsection{Resultados}
A figura \ref{fig:results} contém os gráficos de revocação x precisão para as 30 consultas analisadas.
As consultas são muito distintas, variando em termos de número de termos, complexidade, tema, etc.
Os resultados obtidos também foram bastante diversificados.\\


\begin{figure}[!ht]
\centering
  \subfigure{\epsfig{file=graphics/result_0.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_1.eps, width= 2.6in,height=1.8in}}
\label{fig:results}
\end{figure}
\newpage
\begin{figure}[!ht]
  \subfigure{\epsfig{file=graphics/result_2.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_3.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_4.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_5.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_6.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_7.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_8.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_9.eps, width= 2.6in,height=1.8in}}
\label{fig:results}
\end{figure}
\newpage

\begin{figure}[!ht]
\centering
  \subfigure{\epsfig{file=graphics/result_10.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_11.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_12.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_13.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_14.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_15.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_16.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_17.eps, width= 2.6in,height=1.8in}}
\label{fig:results}
\end{figure}
\newpage
\begin{figure}[!ht]
\centering
  \subfigure{\epsfig{file=graphics/result_18.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_19.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_20.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_21.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_22.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_23.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_24.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_25.eps, width= 2.6in,height=1.8in}}
   \label{fig:results}
\end{figure}
\newpage
\begin{figure}[!ht]
\centering
  \subfigure{\epsfig{file=graphics/result_26.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_27.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_28.eps, width= 2.6in,height=1.8in}}
  \subfigure{\epsfig{file=graphics/result_29.eps, width= 2.6in,height=1.8in}}
\caption{Revocação x Precisão}
  \label{fig:results}
\end{figure}

\noindent Os gráficos mostram que, em quase metade das consultas, os algoritmos indicaram documentos
que não pertencem ao conjunto de relevantes como os mais indicados ao usuário. 
Exemplos disso são os resultados para as pesquisas por ``casa e video'' e ``yahoo''. Este comportamento
é crítico, já que os usuários costumam consultar apenas as primeiras indicações. 
Entretanto, algumas requisições, tais como ``mario'' e ``frases de amor'', tiveram respostas bem avaliadas.\\

\noindent As consultas com melhores resultados são aquelas em que a precisão é alta 
para o máximo de revocação. Ou seja, os valores da curva do gráfico para precisão devem ser 
elevados, principalmente para valores reduzidos de revocação. 
É importante notar que, em geral, os gráficos convergem rapidamente para valores próximos de zero
de precisão. Este comportamento pode ser explicado por dois fatos. Primeiramente, o número de 
documentos relevantes para os testes é, em geral, reduzido, variando de 7 à 28 documentos.
Por outro lado, a coleção possui muitos documentos e, portanto, a quantidade destes que são retornados
por consulta é, em geral, alta. Assim, mesmo que muitos documentos relevantes estejam no topo do {\it ranking},
a curva deve convergir de maneira, relativamente, rápida, já que existem muitas outras indicações que não são relevantes.\\

\noindent Para algumas consultas, a ordenação dos documentos, para os três algoritmos não priorizou os mais relevantes.
A possível explicação é que elas envolvem termos pouco discriminatórios na consulta,
como por exemplo a busca por ``oi'' ou termos pouco relacionados entre si, como em ``casa e video''. 
Podemos observar que os melhores resultados ocorreram para temas bastante específicos, como ``naruto''
e ``ana maria braga'', ou requisições com termos bem relacionados, tal como ``frases de amor''.
O número elevado de termos em uma requisição pode melhorar muito a qualidade da resposta se os termos forem
bem descritivos e relacionados. Entretanto, muitos termos vagos e não coesos prejudicam significativamente a ordenação.
Outras explicações possíveis para as falhas dos algoritmos são definições ruins de documentos relevantes ou problemas no {\it parser} para 
os termos consultados especificamente.

\begin{figure}[!ht]
\centering
   \includegraphics[width=.60\textwidth]{graphics/result_mean.eps}
\caption{Revocação x Precisão Média}
\label{mean}
\end{figure}

\noindent O gráfico \ref{mean} exibe a curva de revocação x precisão média para os três algoritmos analisados.
As observações gerais para as três curvas tornam-se mais evidentes neste gráfico. Também é mais fácil avaliar
a efetividade dos modelos visualizando o comportamento destas curvas. Em geral, os modelos
apresentaram uma curva com comportamento semelhante, o que pode ser uma evidência de que as falhas nos {\it rankings}
estão mais relacionadas com problemas na especificação das consultas ou dos conjuntos de documentos relevantes
do que com alguma deficiência dos algoritmos. A altura das curvas no gráfico evidenciam que, em termos de efetividade,
o algoritmo BM25 se saiu melhor que o modelo combinado, que apresentou melhores resultados que o modelo vetorial.
Entretanto, é importante notar que em algumas consultas especificamente, tais como ``frases de amor'', ``naruto'' e ``vivo'', o modelo combinado 
foi superior.

% \newpage


\section{Conclusão}
É indiscutível a importância de métodos eficientes para tarefas de recuperação de informação no contexto atual.
O Trabalho Prático 1 propôs a implementação de um sistema para geração de arquivo invertido, estrutura que
permite a recuperação rápida de documentos a partir de termos que os compõem. 
O Trabalho Prático 2 complementa o primeiro projeto ao propor
o desenvolvimento de um processador de consultas que interpreta a requisição do usuário e
 retorna um {\it ranking} de documentos mais relacionados com a pesquisa.\\

\noindent O desenvolvimento deste projeto permitiu constatar que os métodos estudados são realmente muito poderosos.
Os experimentos mostraram que é possível obter, quase que instantaneamente, 
um {\it ranking} de documentos potencialmente relevantes para uma dada consulta.
Além disso, a qualidade avaliada da ordenação dos documentos não foi ruim.
Entretanto, existe um potencial de melhoria muito grande, já que muitas
informações relevantes, como os {\it links} entre páginas, não foram consideradas neste trabalho.

\bibliographystyle{plain}
\bibliography{tp1RI}


\end{document}

